package dynamicStudy;

public class DynamicStudy07 {

    /**
     * 题目七：最长有效括号
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     * 总结：一维的初始化一半只是初始化第一个，第一个就是边界
     * 字符串问题是用一维还是用二维，主要看的是一个字符串还是两个字符串
     * 子问题就是前面的数组
     * @param args
     */
    public static void main(String[] args) {

    }

    public static int longestValidParentheses(String s){
        if (s == null || s.length() < 1){
            return 0;
        }
        int len = s.length();
        int maxLen = 0;
        //定义状态数组
        int[] dp = new int[len];
        //进行初始化，确定边界，一维数组一般只确定头元素
        dp[0] = 0; //默认也为0
        //进行循环求值
        for (int i = 1; i < len; i++){
            if (s.charAt(i) == ')'){
                if (s.charAt(i - 1) == '('){
                    dp[i] = (i - 2 >= 0? dp[i - 2]:0) + 2;
                } else {
                    if (i-dp[i-1]>=1 && s.charAt(i -1 -dp[i - 1]) == '('){
                        dp[i] = dp[i-1] + (i-dp[i-1]>=2?dp[i - dp[i-1] -2]:0) + 2;
                    }
                }
            }
        }
        for (int i = 0; i < len; i++){
            if (dp[i] > maxLen){
                maxLen = dp[i];
            }
        }
        return maxLen;
    }
}
